#pragma once

#include "SHash.h"
#include <algorithm>
#if defined (WIN32)
#include <intrin.h>
#elif defined (CCORE_MAC)
#include <sys/malloc.h>
#else
#include <malloc.h>
#endif
#include <functional> 
#include <string>
#include <string.h>
#include <vector>


#if defined(__arm__) || defined(__aarch64__)
#include "sse2neon.h"
#else
#include <emmintrin.h>
#endif

#include "../core.h"

namespace qb{
	namespace base{
		using namespace qb::base;
#define USE_ALIGN
#ifdef USE_ALIGN
#if defined (WIN32)
#define DEL_ALIGN __declspec(align(64))
#define NEW_CACHE(TYPE,ARG) new (_aligned_malloc(sizeof(TYPE), kCacheSize)) TYPE(ARG);
#define DEL_CACHE(TYPE,PTR) if(PTR){PTR->~TYPE();_aligned_free(PTR);}
#elif defined (CCORE_MAC)
#define DEL_ALIGN __attribute__((aligned(64)))
#define NEW_CACHE(PTR,TYPE,ARG) posix_memalign((void**)&PTR, kCacheSize, sizeof(TYPE)); new (PTR) TYPE(ARG);
#define DEL_CACHE(TYPE,PTR) if(PTR){PTR->~TYPE();free(PTR);}
#else
#define DEL_ALIGN __attribute__((aligned(64)))
#define NEW_CACHE(TYPE,ARG) new (memalign(kCacheSize, sizeof(TYPE))) TYPE(ARG);
#define DEL_CACHE(TYPE,PTR) if(PTR){PTR->~TYPE();free(PTR);}
#endif
#else
#define DEL_ALIGN
#define NEW_CACHE(TYPE,ARG) new TYPE(ARG);
#define DEL_CACHE(TYPE,PTR) if(PTR){PTR->~TYPE();delete PTR;}
#endif
		typedef unsigned short ushort;
		typedef unsigned int uint;
		typedef unsigned char uchar;
		typedef int64_t i64;
		static_assert(sizeof(i64) == 8, "");
		using TagVector = __m128i;

#define FOLLY_SAFE_DCHECK(expr, msg)  //BASSERTS(expr,msg)
#define LIKELY(x)   (x)
#define UNLIKELY(x) (x)
#define FOLLY_INTRINSIC_CONSTEXPR const

#ifdef _MSC_VER    // Visual Studio
#  define FOLLY_ALWAYS_INLINE  __forceinline
#else
#  ifdef __GNUC__
#    define FOLLY_ALWAYS_INLINE  inline __attribute__((always_inline))
#  else
#    define FOLLY_ALWAYS_INLINE inline
#  endif
#endif


		// 经过测试,murMurHash的标准差是time33的差不多一半大小,更稳定
		inline unsigned int time33Inline(const char *str, int len){
			unsigned int hash = 5381;
			const char* pend = str + len;
			while (str < pend){
				hash += (hash << 5) + (*str++);
			}
			return (hash & 0x7FFFFFFF);
		}
		#ifdef WIN32
		FOLLY_ALWAYS_INLINE int __builtin_ctz(unsigned int x) {
			unsigned long index;
			return int(_BitScanForward(&index, (unsigned long)x) ? index : 32);
		}
		FOLLY_ALWAYS_INLINE int __builtin_clz(unsigned int x) {
			unsigned long index;
			return int(_BitScanReverse(&index, (unsigned long)x) ? 31 - index : 32);
		}
		#endif
		template <typename T>
		FOLLY_ALWAYS_INLINE static void prefetchAddr(T const* ptr) {
			// _mm_prefetch is x86_64-specific and comes from xmmintrin.h.
			// It seems to compile to the same thing as __builtin_prefetch, but
			// also works on windows.
			_mm_prefetch(static_cast<char const*>(static_cast<void const*>(ptr)), _MM_HINT_T0);
		}

		// findLastSet: return the 1-based index of the highest bit set
		// for x > 0, findLastSet(x) == 1 + floor(log2(x))
		template <class T>
		inline FOLLY_INTRINSIC_CONSTEXPR
			typename std::enable_if<
			(std::is_integral<T>::value &&
			std::is_unsigned<T>::value &&
			sizeof(T) <= sizeof(unsigned int)),
			unsigned int>::type
			findLastSet(T x) {
			// If X is a power of two X - Y = ((X - 1) ^ Y) + 1. Doing this transformation
			// allows GCC to remove its own xor that it adds to implement clz using bsr
			return x ? ((8 * sizeof(unsigned int) - 1) ^ __builtin_clz(x)) + 1 : 0;
		}

		namespace sse{
#define SK_CPU_SSE_LEVEL_SSE1     10
#define SK_CPU_SSE_LEVEL_SSE2     20
#define SK_CPU_SSE_LEVEL_SSE3     30
#define SK_CPU_SSE_LEVEL_SSSE3    31
#define SK_CPU_SSE_LEVEL_SSE41    41
#define SK_CPU_SSE_LEVEL_SSE42    42

#ifdef WIN32
			static inline void getcpuid(int info_type, int info[4]) {
				__cpuid(info, 0);
				__cpuidex(info, 1, 0);
			}
#else
			static inline void getcpuid(int info_type, int info[4]) {
				    uint32_t ebx = 0, edx = 0, ecx = 0, eax = info_type;

					#if defined(__i386__) && defined(__PIC__)
						// If PIC used under 32-bit, EBX cannot be clobbered
						// EBX is saved to EDI and later restored
						__asm__("movl %%ebx, %%edi;"
								"cpuid;"
								"xchgl %%ebx, %%edi;"
								: "=D"(ebx), "+a"(eax), "+c"(ecx), "=d"(edx));
                                        #elif defined(__arm__) || defined(__aarch64__)
                                                ;// TODO: czp
					#else
						__asm__("cpuid;" : "+b"(ebx), "+a"(eax), "+c"(ecx), "=d"(edx));
					#endif

						info[0] = eax;
						info[1] = ebx;
						info[2] = ecx;
						info[3] = edx;
			}
#endif
			static inline int get_SIMD_level() {
				int cpu_info[4] = { 0 };

				getcpuid(1, cpu_info);
				if ((cpu_info[2] & (1 << 20)) != 0) {
					return SK_CPU_SSE_LEVEL_SSE42;
				}
				else if ((cpu_info[2] & (1 << 19)) != 0) {
					return SK_CPU_SSE_LEVEL_SSE41;
				}
				else if ((cpu_info[2] & (1 << 9)) != 0) {
					return SK_CPU_SSE_LEVEL_SSSE3;
				}
				else if ((cpu_info[3] & (1 << 26)) != 0) {
					return SK_CPU_SSE_LEVEL_SSE2;
				}
				else {
					return 0;
				}
			}
			static bool supports_sse2() {
                return false;

            //	static int gSIMDLevel = get_SIMD_level();
            //	return (SK_CPU_SSE_LEVEL_SSE2 <= gSIMDLevel);
			}
		}

		class F14HashToken final {
		public:
			F14HashToken() = default;

			using HashPair = std::pair<std::size_t, uint8_t>;

			explicit F14HashToken(HashPair hp) : hp_(hp) {}
			explicit operator HashPair() const {
				return hp_;
			}

			HashPair hp_;

			template <typename Policy>
			friend class F14TableOld;
		};


		// Iterates a mask, optimized for the case that only a few bits are set
		class SparseMaskIter {
			unsigned mask_;

		public:
			explicit SparseMaskIter(unsigned mask) : mask_{ mask } {}

			FOLLY_ALWAYS_INLINE bool hasNext() {
				return mask_ != 0;
			}

			FOLLY_ALWAYS_INLINE unsigned next() {
				FOLLY_SAFE_DCHECK(hasNext(), "");
				unsigned i = __builtin_ctz(mask_);
				mask_ &= (mask_ - 1);
				return i;
			}
		};

		// Iterates a mask, optimized for the case that most bits are set
		class DenseMaskIter {
			unsigned mask_;
			unsigned index_{ 0 };

		public:
			explicit DenseMaskIter(unsigned mask) : mask_{ mask } {}

			bool hasNext() {
				return mask_ != 0;
			}

			unsigned next() {
				FOLLY_SAFE_DCHECK(hasNext(), "");
				if (LIKELY((mask_ & 1) != 0)) {
					mask_ >>= 1;
					return index_++;
				}
				else {
					unsigned s = __builtin_ctz(mask_);
					unsigned rv = index_ + s;
					mask_ >>= (s + 1);
					index_ = rv + 1;
					return rv;
				}
			}
		};

		// Holds the result of an index query that has an optional result,
		// interpreting a mask of 0 to be the empty answer and the index of the
		// last set bit to be the non-empty answer
		class LastOccupiedInMask {
			unsigned mask_;

		public:
			explicit LastOccupiedInMask(unsigned mask) : mask_{ mask } {}

			bool hasIndex() const {
				return mask_ != 0;
			}

			unsigned index() const {
				//folly::assume(mask_ != 0);
				return findLastSet(mask_) - 1;
			}
		};


		// Holds the result of an index query that has an optional result,
		// interpreting a mask of 0 to be the empty answer and the index of the
		// first set bit to be the non-empty answer
		class FirstEmptyInMask {
			unsigned mask_;

		public:
			explicit FirstEmptyInMask(unsigned mask) : mask_{ mask } {}

			FOLLY_ALWAYS_INLINE bool hasIndex() const {
				return mask_ != 0;
			}

			FOLLY_ALWAYS_INLINE unsigned index() const {
				FOLLY_SAFE_DCHECK(mask_ != 0, "");
				return __builtin_ctz(mask_);
			}
		};

		//针对我们数据,性能比默认的还差
		struct  S_CORE_EXPORT string_less : public std::binary_function<std::string, std::string, bool> {
			//You can use __m128i for sse 128bit compare in x86 & x64, but here we do not use it for convenient.
#ifdef __x86_64__
			typedef  unsigned long long comp_type;
#else
			typedef  unsigned int comp_type;
#endif

			bool operator() (const std::string& x, const std::string& y) const {
				if (x.length() != y.length()){
					return x.length() < y.length();	//inlined function will help us.
				}

				const unsigned int word_size = sizeof(comp_type);
				std::string::size_type length = x.length();
				std::string::size_type cmid = length & (~(word_size - 1));
				std::string::size_type mid = cmid / word_size;

				const comp_type *px = reinterpret_cast<const comp_type*>(x.data());
				const comp_type *py = reinterpret_cast<const comp_type*>(y.data());

				if (cmid != length){
					const unsigned int comp_length_bits = (length & (word_size - 1)) << 3;
					//for little endian
					const comp_type mask_pattern = (1u << comp_length_bits) - 1;
					//for big endian
					//const comp_type mask_pattern = static_cast<comp_type>(-1) << ((word_size << 3) - comp_length_bits);

					const comp_type r1 = px[mid] & mask_pattern;
					const comp_type r2 = py[mid] & mask_pattern;
					if (r1 != r2){
						return r1 < r2;
					}
				}

				while (mid-- != 0){
					const comp_type r1 = px[mid];
					const comp_type r2 = py[mid];
					if (r1 != r2){
						return r1 < r2;
					}
				}
				//equal?
				return false;
			}
		};


		struct LinkedHashMapStat{
			int		slot_count;	// 插槽的个数
			int		slot_hole;	// 插槽为空的个数
			int		bytes;		// 总共占用的内存字节数
			int		count;		// 总共存入的key的个数
			int		hole;		// 所有CacheLine中空洞的总个数
			int		cache;		// 所有CacheLine的总个数
			int		max_level;	// CacheLine链表的最大长度
			double	sum_level;	// 所有CacheLine的长度之和,用于计算平均长度
			LinkedHashMapStat(){ memset(this, 0, sizeof(*this)); }
		};

		template<typename EntryType, typename ValueType>
		class DEL_ALIGN F14LinkedChunk{						// 缓存行的另一种实现
			enum{
				kCapacity = 16,			// 参照folly的F14Table,每个缓存行放置的元素个数
				kDesiredCapacity = kCapacity - 2,
				kFullMask = static_cast<unsigned>(~(~uint64_t{ 0 } << kCapacity))
			};
			typedef LinkedHashMapStat Stat;
			uchar			m_tags[kCapacity];		// 
			F14LinkedChunk*	m_next;					// 
			EntryType		m_items[kCapacity];		// 
		public:
			enum{ kKeyCount = kCapacity };
			F14LinkedChunk(F14LinkedChunk* next) :m_next(next){
				memset(&m_tags[0], '\0', kCapacity*sizeof(uchar));
			}
			void Clear(){
				memset(&m_tags[0], '\0', kCapacity*sizeof(uchar));
				memset(&m_items[0], '\0', kCapacity*sizeof(EntryType));
				m_next = nullptr;
			}
			void SetNext(F14LinkedChunk* next){ m_next = next; }
			inline F14LinkedChunk* GetNext()const{ return m_next; }
			bool Put(const EntryType& key, const ValueType& value, bool update)
			{
				auto hp = splitHash(key.GetHash());
				int index = update?findImpl(hp, key, sse::supports_sse2()):(-1);
				if (index >= 0)
				{
					EntryType& keyValue = m_items[index];
					keyValue = key;
					keyValue.SetValue(value);
					return true;
				}

				auto first = firstEmpty();
				if (first.hasIndex())
				{
					std::size_t itemIndex = first.index();
					setTag(itemIndex, hp.second);
					EntryType& keyValue = m_items[itemIndex];
					keyValue = key;
					keyValue.SetValue(value);
					return true;
				}
				return false;
			}

			bool Get(const EntryType& key, ValueType& value)const
			{
				bool sse2 = sse::supports_sse2();
				auto hp = splitHash(key.GetHash());
				const F14LinkedChunk* chunk = this;
				do
				{
					if (sizeof(F14LinkedChunk) > 64 && sse2)
						prefetchAddr(chunk->itemAddr(8));
					int index = chunk->findImpl(hp, key,sse2);
					if (index >= 0)
					{
						value = chunk->m_items[index].GetValue();
						return true;
					}
					chunk = chunk->m_next;
				} while (chunk);
				return false;
			}

			bool Erase(const EntryType& key)
			{
				auto hp = splitHash(key.GetHash());
				int index = findImpl(hp, key, sse::supports_sse2());
				if (index >= 0){
					clearTag(index);
					return true;
				}
				return false;
			}
			bool IsEmpty()const
			{
				for (int i = 0; i < kCapacity; i++)
				{
					if (m_tags[i] != 0)
						return false;
				}
				return true;
			}
			void GetStat(Stat& st)const{
				st.cache++;
				st.bytes += sizeof(F14LinkedChunk);
				for (int i = 0; i < kCapacity; i++)
				{
					if (m_tags[i] == '\0')
						st.hole++;
					else
						st.count++;
				}
				int level = 1;
				auto next = m_next;
				while (next)
				{
					level++;
					next = next->GetNext();
				}
				if (st.max_level < level)
					st.max_level = level;
				st.sum_level += level;
				if (m_next)
					m_next->GetStat(st);
			}
			EntryType const& citem(std::size_t i) const {
				return *(itemAddr(i));
			}

			DenseMaskIter occupiedIter() const {
				return DenseMaskIter{ occupiedMask() };
			}
		protected:
			using HashPair = F14HashToken::HashPair;
			void setTag(std::size_t index, uint8_t tag) {
				m_tags[index] = tag;
			}
			void clearTag(std::size_t index) {
				m_tags[index] = 0;
			}
			EntryType* itemAddr(std::size_t i) const {
				return static_cast<EntryType*>(
					const_cast<void*>(static_cast<void const*>(&m_items[i])));
			}
			static FOLLY_ALWAYS_INLINE HashPair splitHash(std::size_t hash) {
				uint8_t tag = (hash & 0x000000ff) | 0x80;	// 使用低7个bit用于tag,第8个保留用于识别是否为空
				return std::make_pair(hash, tag);
			}

			FOLLY_ALWAYS_INLINE int findImpl(const HashPair& hp, EntryType const& key,bool sse2) const {
				//使用sse比不使用,提升10%到15%左右,整体上
				if (!sse2)
					return findWithoutSSE(hp, key);
				auto hits = tagMatchIter(hp.second);
				while (hits.hasNext()) {
					auto i = hits.next();
					if (m_items[i].EqualKey(key))
						return i;
				}
				return -1;
			}
			FOLLY_ALWAYS_INLINE int findWithoutSSE(const HashPair& hp, EntryType const& key) const {
				//使用sse比不使用,提升10%到15%左右,整体上
				for (int i = 0; i < kCapacity; i++)
				{
					if (m_tags[i] == hp.second && m_items[i].EqualKey(key))
						return i;
				}
				return -1;
			}
			FOLLY_ALWAYS_INLINE TagVector const* tagVector() const {
				return static_cast<TagVector const*>(static_cast<void const*>(&m_tags[0]));
			}
			FOLLY_ALWAYS_INLINE unsigned occupiedMask() const {
				auto tagV = _mm_load_si128(tagVector());
				return _mm_movemask_epi8(tagV) & static_cast<unsigned>(kFullMask);
			}
			FOLLY_ALWAYS_INLINE FirstEmptyInMask firstEmpty() const {
				return FirstEmptyInMask{ occupiedMask() ^ static_cast<unsigned>(kFullMask) };
			}
			FOLLY_ALWAYS_INLINE SparseMaskIter tagMatchIter(std::size_t needle) const {
				FOLLY_SAFE_DCHECK((needle & 0x80) != 0, "");
				auto tagV = _mm_load_si128(tagVector());
				auto needleV = _mm_set1_epi8(static_cast<uint8_t>(needle));
				auto eqV = _mm_cmpeq_epi8(tagV, needleV);
				auto mask = _mm_movemask_epi8(eqV) & static_cast<unsigned>(kFullMask);
				return SparseMaskIter{ mask };
			}
		};

		template<typename EntryType, typename ValueType>
		class DEL_ALIGN CacheLineArray{			// 刚好一个缓存行,一个缓存行大小为64
			typedef LinkedHashMapStat Stat;		// 
			enum{ kKeyCount = (64 - sizeof(void*)) / sizeof(EntryType) };
			CacheLineArray*	m_next;				// 下一个
			EntryType		m_keys[kKeyCount];	// 
		public:
			CacheLineArray(CacheLineArray* next) :m_next(next)
			{
				for (int i = 0; i < kKeyCount; i++)m_keys[i].Clear();
			}
			~CacheLineArray(){}
			void Clear(){
				memset(&m_keys[0], '\0', kKeyCount*sizeof(EntryType));
				m_next = nullptr;
			}
			void SetNext(CacheLineArray* next){ m_next = next; }
			inline CacheLineArray* GetNext()const{ return m_next; }
			bool Put(const EntryType& key, const ValueType& value, bool update)
			{
				// 如果已经满了,那么添加失败
				// 查找一个空缺的位置,放进去
				if (update)
				{
					CacheLineArray* cur = this;
					while (cur)
					{
						for (int i = 0; i < kKeyCount; i++)
						{
							EntryType& curkey = cur->m_keys[i];
							if (curkey.EqualKey(key))
							{
								curkey.SetValue(value);
								return true;
							}
						}
						cur = cur->m_next;
					}
				}
				for (int i = 0; i < kKeyCount; i++)
				{
					if (m_keys[i].IsEmpty())
					{
						m_keys[i] = key;
						m_keys[i].SetValue(value);
						return true;
					}
				}
				return false;
			}
			bool Get(const EntryType& key, ValueType& value)const
			{
				// 忽略key的bid和hibid
				const CacheLineArray* cur = this;
				do
				{
					const CacheLineArray* next = cur->m_next;
					if (next)
						_mm_prefetch(static_cast<char const*>(static_cast<void const*>(next)), _MM_HINT_T0);
					const EntryType* keys = cur->m_keys;
					for (int i = 0; i < kKeyCount; i++)
					{
						if (keys[i].EqualKey(key))
						{
							value = keys[i].GetValue();
							return true;
						}
					}
					cur = next;
				} while (cur);
				return false;
			}
			bool Erase(const EntryType& key)
			{
				// 返回值:true,表示成功删除,不递归,是否为空并删除,交给上层来控制
				for (int i = 0; i < kKeyCount; i++)
				{
					if (m_keys[i].EqualKey(key))
					{
						m_keys[i].Clear();
						return true;
					}
				}
				return false;
			}
			void GetStat(Stat& st)const
			{
				st.cache++;
				st.bytes += sizeof(CacheLineArray);
				for (int i = 0; i < kKeyCount; i++)
				{
					if (m_keys[i].IsEmpty())
						st.hole++;
					else
						st.count++;
				}
				int level = 1;
				CacheLineArray* next = m_next;
				while (next)
				{
					level++;
					next = next->GetNext();
				}
				if (st.max_level < level)
					st.max_level = level;
				st.sum_level += level;
				if (m_next)
					m_next->GetStat(st);
			}
			bool IsEmpty()const
			{
				for (int i = 0; i < kKeyCount; i++)
				{
					if (!m_keys[i].IsEmpty())
						return false;
				}
				return true;
			}
			EntryType const& citem(std::size_t i) const {
				return m_keys[i];
			}
			DenseMaskIter occupiedIter() const {
				return DenseMaskIter{ occupiedMask() };
			}
			FOLLY_ALWAYS_INLINE unsigned occupiedMask() const {
				enum{
					kCapacity = 16,			// 参照folly的F14Table,每个缓存行放置的元素个数
					kFullMask = static_cast<unsigned>(~(~uint64_t{ 0 } << kCapacity))
				};
				uchar			tags[kCapacity];
				memset(&tags[0], '\0', kCapacity*sizeof(uchar));
				for (int i = 0; i < kKeyCount;i++)
				{
					if (!m_keys[i].IsEmpty())
						tags[0] = 0x80;
				}
				auto tagV = _mm_load_si128(static_cast<TagVector const*>(static_cast<void const*>(&tags[0])));
				return _mm_movemask_epi8(tagV) & static_cast<unsigned>(kFullMask);
			}
		};



		/*
		有两个模板参数
		EntryType	用于键和值放在一起的结构体,对于部分需要值域键紧密结合的,如
		ComBondKey中值的高6位在键结构体中,需要实现的接口,参见EntryTypeDefault
		ValueType	值结构体

		实现:
		哈希冲突时,以单链表的形式挂在


		*/
		template<
			typename EntryType,
			typename ValueType,
			typename CacheLine = F14LinkedChunk<EntryType, ValueType >
		>
		class LinkedHashMap{
		public:
			enum{
				kCacheSize = 64,		// 一级缓存行大小通用值为64字节
				kBitCountMin = 6,		//
				kBitCountMax = 24,		// 限制哈希插槽最大值为1<<24,即16777216
				//kKeyCount = (kCacheSize - sizeof(void*)) / sizeof(EntryType),
				//一个缓存行CacheLine中放置几个值项
			};
			typedef LinkedHashMapStat Stat;
		protected:
			class EntryTypeDefault{	//仅供阅读,EntryType需要实现的接口
			public:
				bool IsEmpty()const = 0;
				unsigned int GetHash()const = 0;
				bool EqualKey(const EntryTypeDefault& key)const = 0;
				const ValueType& GetValue()const = 0;
				void SetValue(const ValueType& value) = 0;
			};
			typedef CacheLine* SlotPtr;
			typedef std::vector<SlotPtr> SlotArray;
		protected:
			SlotArray	m_slots;		// m_slot_count个
			int			m_bitcount;		// 1<<m_bitcount 即为插槽个数
			int			m_bitmask;		// 1<<m_bitcount-1 用于表示掩码,用于计算插槽位置
			int			m_count;		// 真实放入的键值对个数
			int			m_nodecount;	// CacheLine的个数
			bool		m_sse2;
		public:
			LinkedHashMap(int capBits = 13) :m_count(0), m_nodecount(0),
				m_sse2(sse::supports_sse2())
			{
				// 经过测试,对于20w的数据1w个插槽是合适的,效率和内存综合最佳
				//NameDict插入时间性能有待优化, 改成哈希表可能更好
				//	CacheLine是整块的内存, 可以预先提前分配
				//	bkey可以使用编码进一步减少尺寸
				//	参考F14Map, 使用并行搜索, 增大CacheLine尺寸会导致空间浪费
				//F14Map并行搜索 : 为每个节点生成一个1个字节的哈希值, 将16个节点的哈希值凑成一个128位值, 然后使用intel sse指令
				//			 一次性搜索16个
				m_bitcount = capBits<kBitCountMin ? kBitCountMin : (capBits>kBitCountMax ? kBitCountMax : capBits);
				m_bitmask = (1 << m_bitcount) - 1;
				int capcity = 1 << m_bitcount;
				m_slots.reserve(capcity);
				for (int i = 0; i < capcity; i++)
					m_slots.emplace_back(nullptr);
			}
			~LinkedHashMap()
			{
				for (int i = 0; i < (int)m_slots.size(); i++)
				{
					CacheLine* cache = m_slots[i];
					while (cache)
					{
						CacheLine* temp = cache;
						cache = cache->GetNext();
						DEL_CACHE(CacheLine, temp);
						m_nodecount--;
					}
				}
			}
			int GetCount()const{ return m_count; }
			int GetBitCount()const{ return m_bitcount; }
			int GetLength()const{ return m_slots.capacity(); }
			int GetSlotCount()const{ return m_slots.size(); }
			double GetLoadRatio()const{
				return m_count*1.0 / (m_nodecount*CacheLine::kKeyCount);
			}
		public:
			bool Get(const EntryType& key, ValueType& value)const
			{
				int slot = GetPos(key);
				SlotPtr cache = m_slots[slot];
				if (cache)
				{
					//_mm_prefetch(static_cast<char const*>(static_cast<void const*>(cache)), _MM_HINT_T0);
					return cache->Get(key, value);
				}

				return false;
			}

			void Put(const EntryType& keyValue, const ValueType& value)
			{
				int slot = GetPos(keyValue);
				SlotPtr first = m_slots[slot];
				SlotPtr cache = first;
				while (cache)
				{
					if (cache->Put(keyValue, value, true))
					{
						m_count++;
						return;
					}
					cache = cache->GetNext();
				}
#if defined (CCORE_MAC)
                NEW_CACHE(cache, CacheLine, first);
#else
                cache = NEW_CACHE(CacheLine, first);
#endif

				cache->Put(keyValue, value, false);
				m_slots[slot] = cache;
				m_nodecount++;
				m_count++;
			}
			bool Erase(const EntryType& keyValue)
			{
				bool suc = false;
				SlotPtr prev = nullptr;
				int slot = GetPos(keyValue);
				SlotPtr cache = m_slots[slot];
				while (cache)
				{
					suc = cache->Erase(keyValue);
					if (suc )
					{
						if(cache->IsEmpty())
						{
							if (prev == nullptr)
								m_slots[slot] = cache->GetNext();
							else
								prev->SetNext(cache->GetNext());
							DEL_CACHE(CacheLine, cache);
							m_nodecount--;
						}
						break;
					}
					prev = cache;
					cache = cache->GetNext();
				}
				if (suc)
					m_count--;
				return suc;
			}
			void Expand(int capBits)
			{
				int bitcount = capBits<kBitCountMin ? kBitCountMin : (capBits>kBitCountMax ? kBitCountMax : capBits);
				if (bitcount == m_bitcount)
					return;
				LinkedHashMap temp(capBits);
				SlotPtr head = nullptr;
				for (int i = 0; i < (int)m_slots.size(); i++)
				{
					SlotPtr next = m_slots[i];
					while (next)
					{
						SlotPtr cache = next;
						next = next->GetNext();
						cache->SetNext(nullptr);

						DenseMaskIter itor = cache->occupiedIter();
						while (itor.hasNext())
						{
							auto i = itor.next();
							const EntryType& key = cache->citem(i);
							head=temp.PutWithCache(key, key.GetValue(), head);
						}
						// 放到空闲单链表中
						cache->SetNext(head);
						head = cache;
					}
				}
				// 清除head的单链表
				while (head)
				{
					CacheLine* temp = head;
					head = head->GetNext();
					DEL_CACHE(CacheLine, temp);
				}
				Swap(temp);
			}
			void Swap(LinkedHashMap& temp)
			{
				std::swap(m_slots, temp.m_slots);
				std::swap(m_bitcount, temp.m_bitcount);
				std::swap(m_bitmask, temp.m_bitmask);
				std::swap(m_count, temp.m_count);
				std::swap(m_nodecount, temp.m_nodecount);
			}
		protected:
			// 优先使用cacheList单链表来分配CacheLine,如果使用,消耗头部,返回下一个
			// 如果不使用,直接返回下一个,其他情况,与原先的Put相同
			CacheLine* PutWithCache(const EntryType& keyValue, const ValueType& value, CacheLine* cacheList)
			{
				int slot = GetPos(keyValue);
				SlotPtr cache = m_slots[slot];
				if (!(cache && cache->Put(keyValue, value, true)))
				{
					if (cacheList)
					{
						cache = cacheList;
						cacheList = cacheList->GetNext();
						cache->Clear();
					}
					else
#if defined (CCORE_MAC)
                        NEW_CACHE(cache, CacheLine, cache);
#else
						cache = NEW_CACHE(CacheLine, cache);
#endif
					m_slots[slot] = cache;
					cache->Put(keyValue, value, false);
					m_nodecount++;
				}
				m_count++;
				return cacheList;
			}

		public:
			inline int GetPos(const EntryType& keyValue)const{
				unsigned int nhash = keyValue.GetHash();
				return (nhash >> m_bitcount)&m_bitmask;
			}
			int  GetBytes()const{
				Stat st;
				GetStat(st);
				return st.bytes;
			}
			void  GetStat(Stat& st)const
			{
				int slot_hole = 0;
				for (int i = 0; i < (int)m_slots.size(); i++)
				{
					CacheLine* cache = m_slots[i];
					if (cache)
						cache->GetStat(st);
					else
						slot_hole++;
				}
				st.slot_hole = slot_hole;
				st.slot_count = m_slots.size();
				st.bytes += m_slots.size()*sizeof(SlotPtr);
			}
		};

	}//namespace base;
}//namespace ss;
